#include <bitset>
#include <cstdio>
#include <deque>
#include <iostream>
#include <istream>
#include <queue>
#include <vector>
using ll = int64_t;
#define sl static inline
#define printf
const ll maxm=2e5+5,inf=1e9+7;
ll n,m,k,p,nt,d[maxm],dp[maxm][57];
bool isn,vis[maxm][57];
struct E{
    ll v,w;
};
struct P{
    ll now,step;
    inline bool operator<(const P&o)const{
        return step>o.step;
    }
};
std::vector<std::vector<E>> edg,re;
std::deque<P>dq;

sl ll dj(){
    for(ll i=1;i<=n;i++){
        d[i]=inf;
    }
    std::priority_queue<P> pq;
    pq.emplace(1,0);
    while(pq.size()){
        auto[now,step]=pq.top();
        // printf("dj now=%lld, step=%lld\n",now,step);
        pq.pop();
        if(step>=d[now])continue;
        d[now]=step;
        for(auto[v,w]:edg[now]){
            pq.emplace(v,step+w);
        }
    }
    
    printf("d[]:");
    for(ll i=1;i<=n;i++){
        printf("%lld ",d[i]);
    }
    printf("\n");
    return d[n]==inf?-1:d[n];
}

sl ll dfs(ll u,ll k){
    if(k<0||k>::k)return 0;
    if(vis[u][k]){
        isn=true;
        return 0;
    }
    if(dp[u][k]!=-1){
        printf("dp[%lld][%lld]=%lld, in temp\n",u,k,dp[u][k]);
        return dp[u][k];
    }
    vis[u][k]=true;
    ll nans=0;
    for(auto[v,w]:re[u]){
        ll nk=d[u]+k-d[v]-w;
        if(nk<0||nk>::k)continue;
        nans=(nans+dfs(v, nk))%p;
        if(isn){
            vis[u][k]=false;
            return 0;
        }
    }
    if(u==1){
        const ll ret= k==0?1:0;
        printf("dp[%lld][%lld]=%lld u==1\n",u,k,ret);
        nans=ret;
    }
    vis[u][k]=false;
    printf("dp[%lld][%lld]=%lld\n",u,k,nans);
    return dp[u][k]=nans;
}

sl void solve(){
    printf("NT = %lld\n",++nt);
    std::cin>>n>>m>>k>>p;
    isn=false;
    edg.clear();
    edg.resize(n+1);
    re.clear();
    re.resize(n+1);
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<=k;j++){
            dp[i][j]=-1;
            vis[i][j]=false;
        }
    }
    for(ll i=1;i<=m;i++){
        ll u,v,w;
        std::cin>>u>>v>>w;
        edg[u].emplace_back(v,w);
        re[v].emplace_back(u,w);
    }
    const ll d = dj();
    printf("found d=%lld\n",d);
    if(d==-1){
        std::cout<<"0\n";
        return;
    }
    // const ll ms=d+k;
    ll ans=0;
    for(ll i=0;i<=k;i++){
        printf("DFS i=%lld----\n",i);
        ans=(ans+dfs(n,i))%p;
        if(isn){
            std::cout<<"-1\n";
            return;
        }
    }
    std::cout<<ans<<"\n";
}

int main(){
    std::iostream::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll t;
    std::cin>>t;
    while(t--){
        solve();
    }
}